#include "diffie_hellman.h"
#include <QDebug>
#include <QTime>
#include <qcoreapplication.h>
#include <QCoreApplication>
#include <QDateTime>
#include <iostream>
#include <vector>
diffie_hellman::diffie_hellman()
{

}
/*
    流程：
    1.生成素数p
    2.求元根g
    3.通过随机数生成A或B
    4.通过收到的B或A，和生成的A或B计算密钥
*/

int diffie_hellman::BianaryTransform(int num, int bin_num[])
{

    int i = 0,  mod = 0;
    //转换为二进制，逆向暂存temp[]数组中
    while(num != 0)
    {
        mod = num%2;
        bin_num[i] = mod;
        num = num/2;
        i++;
    }
    //返回二进制数的位数
    return i;
}
//模重复平方算法
long long diffie_hellman::Modular_Exonentiation(long long a, int b, int n)
{
    int c = 0, bin_num[1000];
    long long d = 1;
    int k = BianaryTransform(b, bin_num)-1;

    for(int i = k; i >= 0; i--)
    {
        c = 2*c;
        d = (d*d)%n;
        if(bin_num[i] == 1)
        {
            c = c + 1;
            d = (d*a)%n;
        }
    }
    return d;
}
int diffie_hellman::Exgcd(int m,int n,int &x)
{
    int x1,y1,x0,y0, y;
    x0=1; y0=0;
    x1=0; y1=1;
    x=0; y=1;
    int r=m%n;
    int q=(m-r)/n;
    while(r)
    {
        x=x0-q*x1; y=y0-q*y1;
        x0=x1; y0=y1;
        x1=x; y1=y;
        m=n; n=r; r=m%n;
        q=(m-r)/n;
    }
    return n;
}
// 生成伪素数
size_t diffie_hellman::Pseudoprime()
{
    int MAX_ROW = 50;
    bool ifprime = false;
    size_t a = 0;
    int arr[MAX_ROW];   //数组arr为{3，4，5，6...52}
    for (int i = 0; i<MAX_ROW; ++i)
    {
        arr[i] = i+3;
    }
    while (!ifprime)
    {
        srand((unsigned)time(0));
        ifprime = true;
        a = ((rand()+30)%50000)*2+50003; //生成一个范围在50003到100003里的奇数
        for (int j = 0; j<MAX_ROW; ++j)
        {
            if (a%arr[j] == 0)//如果a可以被arr中的一个数整除，则a不是素数
            {
                ifprime = false;
                break;
            }
        }
    }
    return a;
}
//Miller-Rabin素数检测
bool diffie_hellman::rabinmiller(size_t n, size_t k)
{

    int s = 0;
    int temp = n-1;
    while ((temp & 0x1) == 0 && temp)
    {
        temp = temp>>1;
        s++;
    }   //将n-1表示为(2^s)*t
    size_t t = temp;

    while(k--)  //判断k轮误判概率不大于(1/4)^k
    {
        srand((unsigned)time(0));
        size_t b = rand()%(n-2)+2; //生成一个b(2≤a ≤n-2)

        size_t y = Modular_Exonentiation(b,t,n);
        if (y == 1 || y == (n-1))
            return true;
        for(int j = 1; j<=(s-1) && y != (n-1); ++j)
        {
            y = Modular_Exonentiation(y,2,n);
            if (y == 1)
                return false;
        }
        if ( y != (n-1))
            return false;
    }
    return true;
}
size_t diffie_hellman::getyuangen(size_t p) {//遍历生成原根
    int count=0;
    std::vector<size_t> fact;
    size_t phi = p - 1;
    size_t n = phi;
    for (size_t i = 2; i * i <= n; ++i) {
        if (n % i == 0) {
            fact.push_back(i);
            while (n % i == 0) n /= i;
        }
    }
    if (n > 1) fact.push_back(n);
    for (size_t res = 2; res <= p; ++res) {
        bool ok = true;
        for (size_t factor : fact) {
            if (Modular_Exonentiation(res, phi / factor, p) == 1) {
                ok = false;
                if(count<3){
                count++;
                }else{
                break;
                }
            }
        }
        if (ok) {
            return res;
            break;}
    }
    return -1;
}
int diffie_hellman::DH_Delay(){
    QTime dieTime = QTime::currentTime().addMSecs(3197);
    while( QTime::currentTime() < dieTime )
       QCoreApplication::processEvents(QEventLoop::AllEvents, 100);
    return 0;
}

void diffie_hellman::DH_Initialize(){//客户端生成g，p，A,KA
flag1:
   DH_Delay();
   while(true){
   p = Pseudoprime();
   if(rabinmiller(p,10)){
       break;
   }
   }
   qDebug()<<"p="<<p;
   g=getyuangen(p);
   qDebug()<<"g="<<g;
   if(g==0)goto flag1;
   srand((unsigned)time(0));
   int p1=p-2;
   if(g<5){
       goto flag1;
   }
   flag2:
   DH_Delay();
   A = (rand()%p1)+2; //生成一个范围在1到p-2里的奇数A
   qDebug()<<"A="<<A;
   if(A==1||A==2)goto flag2;
   KA=Modular_Exonentiation(g,A,p);
   qDebug()<<"KA="<<KA;
   return;
}
int diffie_hellman::server_get_key(){//服务器接受到KA，生成B，KB,并获得密钥K
    qDebug()<<"=======set B and get key============";
    srand((unsigned)time(0));
    int p1=p-2;
    flag:
    DH_Delay();
    B = (rand()%p1)+2; //生成一个范围在1到p-2里的奇数B
    qDebug()<<"B="<<B;
    if(B==2)goto flag;

    KB=Modular_Exonentiation(g,B,p);
    qDebug()<<"KB="<<KB;
    K=Modular_Exonentiation(KA,B,p);
    qDebug()<<"K="<<K;
    return K;
}
int diffie_hellman::client_get_key(){//客户端接受到KB并获得K
    qDebug()<<"====have KB and get K===========";
    K=Modular_Exonentiation(KB,A,p);
    qDebug()<<"K="<<K;
    return K;
}
